// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import (
	"fmt"
)

func HIndex(array []int) int {
	quickSort(array, 0, len(array)-1)
	hIndex := 0
	for i := len(array) - 1; i >= 0; i-- {
		if array[i] >= len(array)-i {
			hIndex++
		} else {
			break
		}
	}
	return hIndex
}

func quickSort(array []int, low, high int) {
	if low >= high {
		return
	}
	p := partition(array, low, high)
	quickSort(array, low, p-1)
	quickSort(array, p+1, high)
}

func partition(array []int, low, high int) int {
	pivot := array[high]
	i := low - 1
	for j := low; j < high; j++ {
		if array[j] < pivot {
			i++
			array[j], array[i] = array[i], array[j]
		}
	}
	array[i+1], array[high] = array[high], array[i+1]
	return i + 1
}

func main() {
	array := []int{33, 23, 56, 7, 8, 18, 99, 28}
	res := HIndex(array)
	fmt.Println(res)
	fmt.Println(array)
}

//$ go run interview6-10.go
//7
//[7 8 18 23 28 33 56 99]
